首先有一个性质

对于 $n \ge 11$，操作 $1$ 必定有解

一个来自 $\text{Okami}$ 的严谨证明：

考虑互不相同的数 $x, y, z, …$，则有

1
2
3
x
x y x+y
x y z x+y x+z y+z x+y+z

也就是对于 $n$ 个互不相同的数它们显然可以拼出 $2^n - 1$，那么根据抽屉原理，则有 $2^n - 1 \ge 1000$ 时必定有解，则命题成立

那么剩下的就直接 $\text{bitset}$ 优化背包就好了（注意可以直接背包因为若集合 $X$ 和 $Y$ 同时选了一个数，那么它们同时去除该数也是相等的），至于操作 $2$ 的影响则直接树状数组统计每个数要立方几次，由于 $\bmod V$，那么直接倍增处理即可

单词询问复杂度 $O (\frac{(r - l + 1)^2V}{32})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>

using namespace std;

const int MAXN = 1e05 + 10;
const int MAXV = 1000 + 10;

int N, M, V;
int a[MAXN]= {0};

int powv[MAXV][25]= {0};
void init () {
	for (int i = 0; i < V; i ++) powv[i][0] = i * i * i % V;
	for (int j = 1; j <= 18; j ++)
		for (int i = 0; i < V; i ++)
			powv[i][j] = powv[powv[i][j - 1]][j - 1];
}
inline int calc (int x, int p) {
	for (int j = 19; j >= 1; j --)
		if (p & (1 << (j - 1)))
			x = powv[x][j - 1];
	return x + 1;
}

int subsum[MAXN]= {0};
inline int lowbit (int x) {
	return x & (- x);
}
void add (int x, int delta) {
	while (x <= N) {
		subsum[x] += delta;
		x += lowbit (x);
	}
}
int query (int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += subsum[x];
		x -= lowbit (x);
	}
	return cnt;
}

bitset<12 * MAXV> f;

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum (), M = getnum (), V = getnum ();
	for (int i = 1; i <= N; i ++)
		a[i] = getnum ();
	init ();
	for (int q = 1; q <= M; q ++) {
		int opt = getnum (), l = getnum (), r = getnum ();
		if (opt == 1) {
			if (r - l + 1 >= 12) puts ("Yuno");
			else {
				f.reset(); bool suc = false; f[0] = 1;
				for (int i = l; i <= r; i ++) {
					int x = calc (a[i], query (i));
					if ((f & (f << x)).any()) {
						suc = true; break;
					}
					f = f | (f << x);
				}
				suc ? puts ("Yuno") : puts ("Yuki");
			}
		}
		else add (l, 1), add (r + 1, - 1);
	}

	return 0;
}

/*
20 20 152
3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58
2 1 17
2 6 12
1 1 12
2 3 5
2 11 11
2 7 19
2 6 15
1 5 12
1 1 9
1 10 19
2 3 19
2 6 20
2 1 13
2 1 15
2 1 9
1 1 1
2 1 7
2 7 19
2 6 19
2 3 6
*/